package com.lun.swordtowardoffer2.c10;

public class FindMaxXOR {

	static class TrieNode{
		TrieNode[] children;

		public TrieNode() {
			this.children = new TrieNode[2];
		}
	}
	
	public TrieNode buildTrie(int[] nums) {
		TrieNode root = new TrieNode();
		
		for(int num : nums) {
			TrieNode node = root;
			for(int i = 31; i > -1; i--) {
				int bit = (num >> i) & 1;
				if(node.children[bit] == null) {
					node.children[bit] = new TrieNode();
				}
				node = node.children[bit];
			}
		}
		return root;
	}
	
	public int findMaxXor(int[] nums) {
		TrieNode root = buildTrie(nums);
		int max = 0;
		
		for(int num : nums) {
			TrieNode node = root;
			int xor = 0;
			
			for(int i = 31; i > -1; i--) {
				int bit = (num >> i) & 1;
				
				if(node.children[1 - bit] != null) {//0的话找1，1的话找0
					xor = (xor << 1) + 1;
					node = node.children[1 - bit];
				}else {//这分支看起来似非而是，没有的反，就只有接受了已有的
					xor <<= 1;
					node = node.children[bit];
				}
			}
			max = Math.max(xor, max);
		}
		return max;
	}
	
}
